package com.mashibing.class23;

/**
 * N皇后问题是指在N*N的棋盘上要摆N个皇后，
 * 要求任何两个皇后不同行、不同列， 也不在同一条斜线上
 *   给定一个整数n，返回n皇后的摆法有多少种。  n=1，返回1
 * n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0
 * n=8，返回92
 */
public class Code03_NQueens {
    public static int num1(int n) {
        if (n < 1) {
            return 0;
        }
        int[] record = new int[n];
        return process1(0, record, n);
    }

    // 当前来到i行，一共是0~N-1行
    // 在i行上放皇后，所有列都尝试
    // 必须要保证跟之前所有的皇后不打架
    // int[] record record[x] = y 之前的第x行的皇后，放在了y列上
    // 返回：不关心i以上发生了什么，i.... 后续有多少合法的方法数
    public static int process1(int i, int[] record, int n) {
        if (i == n) { // i 行号到了终止行, 代表发现了有效方案.
            return 1;
        }
        int res = 0;
        // i行的皇后，放哪一列呢？j列，j列的位置在哪里呢, 逐列尝试.
        for (int j = 0; j < n; j++) {
            if (isValid(record, i, j)) { // 将i行的皇后放到i行j列上, 看一下是否与之前的皇后打架.
                record[i] = j;  // 如果不打架, 就将i行的皇后放到i行j列上.
                res += process1(i + 1, record, n);
            }
        }
        return res;
    }

    public static boolean isValid(int[] record, int i, int j) {
        // 0..i-1 从0行到i-1行, 逐一进行尝试, 判断当前行
        for (int k = 0; k < i; k++) {
            // 共列 j == record[k]
            // 共斜线 Math.abs(record[k] - j) == Math.abs(i - k)
            if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
                return false;
            }
        }
        return true;
    }

    // 请不要超过32皇后问题
    public static int num2(int n) {
        if (n < 1 || n > 32) { // 只能计算 1 - 31 皇后
            return 0;
        }
        // 如果你是13皇后问题，limit 最右13个1，其他都是0
        // 如果你是12皇后问题，limit 最右12个1，其他都是0
        // 1 << 4 : 10000
        // (1 << 4)-1 : 1111
        int limit = n == 32 ? -1 : (1 << n) - 1;
        return process2(limit, 0, 0, 0);
    }

    // 7皇后问题  使用位运算完成.
    // limit : 0....0 1 1 1 1 1 1 1
    // 之前皇后的列影响：colLim
    // 之前皇后的左下对角线影响：leftDiaLim
    // 之前皇后的右下对角线影响：rightDiaLim
    public static int process2(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
        if (colLim == limit) {
            return 1;
        }
        // pos中所有是1的位置，是你可以去尝试皇后的位置
        /**
         * 例如 limit :  (31-8bit值为0)  (0 1 1 1 1 1 1 1)
         * colLimit  :  (31-8bit值为0)  (0 0 1 0 0 0 0 0)
         * leftDiaLim:  (31-8bit值为0)  (0 1 0 0 0 0 0 0)
         * rightDiaLim: (31-8bit值为0)  (0 0 0 1 0 0 0 0)
         * (colLim | leftDiaLim | rightDiaLim) : (31-8bit值为0)  (0 1 1 1 0 0 0 0)
         * ~(colLim | leftDiaLim | rightDiaLim): (31-8bit值为1)  (1 0 0 0 1 1 1 1)
         * limit                                    : (31-8bit值为0)  (0 1 1 1 1 1 1 1)
         * & (~(colLim | leftDiaLim | rightDiaLim)) : (31-8bit值为1)  (1 0 0 0 1 1 1 1)
         * ----------------------------------------------------------------------------
         *  pos :                                     (31-8bit值为0)  (0 0 0 0 1 1 1 1)
         */
        int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
        // mostRightOne 存储最右侧的 1.
        int mostRightOne = 0;
        int res = 0;
        while (pos != 0) {
            // 提取pos的最右侧的 1.
            mostRightOne = pos & (~pos + 1);
            // 将最右侧的1 减掉
            pos = pos - mostRightOne;
            // 尝试放法树.
            res += process2(limit,                          // 限制信息
                    colLim | mostRightOne,                  // 列限制
                    (leftDiaLim | mostRightOne) << 1,       // 左下限制
                    (rightDiaLim | mostRightOne) >>> 1);    // 右下限制.
        }
        return res;
    }

    public static void main(String[] args) {
        int n = 15;

        long start = System.currentTimeMillis();
        System.out.println(num2(n));
        long end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + "ms");

        start = System.currentTimeMillis();
        System.out.println(num1(n));
        end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + "ms");

    }
}
